package com.wyw.leetcode.learning.simple;

import java.util.HashMap;
import java.util.Map;

/**
 * leetcode topic 70
 *  爬楼梯
 *      假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *      每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * @Author Mr Wu yewen.wu.china@gmail.com
 * @Date 2023/2/22 14:39
 */
public class Topic070 {

    static Map<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) {
        System.out.println(climbStairs(5));
    }

    // 动态规划
    public static int climbStairs(int n) {
        // 最开始会想到暴力递归，但是产生一个问题就是会有重复计算，随着深度增加，计算次数指数倍增长（O(2^n)）
        /*
            暴力递归
         */
//        if(n == 1)
//            return 1;
//        if(n == 2)
//            return 2;
//
//        return climbStairs(n-1) + climbStairs(n-2);

        /*
            记录旧的数据，这样省去了多次计算 （O(n)）
         */
        // 用于存储计算过的深度结果
//        if(n == 1)
//            return 1;
//        if(n == 2)
//            return 2;
//
//        if(map.get(n)!=null) {
//            return map.get(n);
//
//        } else {
//            int num = climbStairs(n - 1) + climbStairs(n - 2);
//            map.put(n, num);
//            return num;
//        }

        /*
            自底向上动态规划
         */
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;

        int a = 1;
        int b = 2;
        int temp = 0;

        for(int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        return temp;


    }
}
